Skip to main content

Binary Search

Binary Search Loop​

def search(nums, target):
        low, high = 0, len(nums)-1
        while low <= high:
            mid = (low+high) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                high = mid -1
            else:
                low = mid + 1
        return -1

print(search([1,2,3,4,5,6], 4))

Binary Search Recursion​

  • Note that although the concept is fairly simple, getting all the details right is far more difficult than you might think. Pay attention to the plus ones and minus ones.
def search(nums, target, low, high):
	if low > high:
		return -1
	mid = (low + high) // 2
	if nums[mid] == target:
		return mid
	elif nums[mid] > target:
		return search(nums, target, low, mid-1)
	else:
		return search(nums, target, mid+1, high)

print(search([1,2,3,4,5,6], 4, 0, 6))

Bug with Binary Search and Merge Sort​

  • where is the bug/problem
    • mid = (low + high) // 2
  • how is the bug happening
    • if the sum of low and high is greater than the maximum positive int value (2^31 - 1). The sum overflows to a negative value, and the value stays negative when divided by two
    • This can cause
      • Index out of bound exception, in Java
      • in python this can cause, unexpected result
  • what inputs can cause the bug?
    • this bug can manifest itself for arrays whose length (in elements) is 2^30 or greater (roughly a billion elements).
  • What is the best way to calculate mid then?
int mid = low + ((high - low) / 2);

int mid = (low + high) >>> 1;  #faster and clean [recommended]

int mid = (low + high) >> 1;  #for python

mid = ((unsigned int)low + (unsigned int)high)) >> 1; #for c and c+=

Resource​